package com.dmall.sort.algorithm;

import java.util.Random;

/**
 * 三路快速排序算法
 * 三路快速排序算法可以在任何数组情况下保证算法的时间复杂度不会超过O(nlogn)
 * 并且如果数组的元素都一样的情况下，可以让算法的时间复杂度变为O(n)
 * @author xiao1.wang
 * @date 2021/10/10 17:40
 */
@SuppressWarnings("all")
public class ThreeWaysQuickSort implements Sort {

    private static final Random RANDOM = new Random();

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int[] range = new int[2];
        partition(arr, l, r, range);
        quickSort(arr, l, range[0] - 1);
        quickSort(arr, range[1] + 1, r);
    }

    private void partition(int[] arr, int l, int r, int[] range) {
        int random = RANDOM.nextInt(r - l + 1) + l;
        swap(arr, random, r);

        // arr[l+1...lt) < v; arr[lt...gt] == v; arr(gt...r] > v
        int lt = l + 1, gt = r, i = lt;
        while (i <= gt) {
            if (arr[i] < arr[l]) {
                swap(arr, lt ++, i ++);
            } else if (arr[i] > arr[l]) {
                swap(arr, gt --, i);
            } else {
                i ++;
            }
        }
        swap(arr, l, lt - 1);
        range[0] = lt;
        range[1] = gt;
    }

    @Override
    public String getName() {
        return "三路快速排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new ThreeWaysQuickSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
